package algorithmlearn;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 两个一样长的数组a：[1，2，5，1，7….] b：[xxxxx]
 * a 里取m 个 ，b里取n 个，（m，n是给定值，m+n小于等于数组的length），
 * 要求取数据时两边不能取索引同一位置的，
 * 求取到的m+n个数的和的最大值
 * a { 10 , 8, 2 }  b { 9, 2 , 1}   m:1  n:1
 * 动态规划 fun(m,n) = max(fun(m-1,n)+a , fun(m,n-1)+b)
 * @Auther: eii
 * @Date: 2020/8/18 14:04
 * @Description:
 */
public class ArrMax {

    public static void main(String[] args) {
        int[] a = {10, 8, 5, 1};
        int[] b = {20, 6, 3, 2};
        int m = 1;
        int n = 2;

        List<Node> total = megerArr(a, b);
        boolean[][][] usedTable = initUsedTable(m, n, total);

        int max = getMaxNum(m, n, total, usedTable);
        boolean[] useInde = usedTable[m][n];
        System.out.println(max);
        System.out.println(useInde);
    }

    static int getMaxNum(int m, int n, List<Node> total, boolean[][][] usedTable) {
        if (m == 0) {
            return 1;
        }
        if (n == 0) {
            return 1;
        }
        int premd = getMaxNum(m - 1, n, total, usedTable);
        Node anode = getIndexViaIsA(total, usedTable[m - 1][n], true);
        int maxPrem = premd + anode.val;

        getMaxNum(m, n - 1, total, usedTable);
        Node bnode = getIndexViaIsA(total, usedTable[m][n - 1], false);
        int maxPren = premd + bnode.val;

        if(maxPrem >= maxPren){
            usedTable[m][n] = usedTable[m - 1][n].clone();
            usedTable[m][n][anode.index] = true;
            return maxPrem;
        }else{
            usedTable[m][n] = usedTable[m][n - 1].clone();
            usedTable[m][n][bnode.index] = true;
            return maxPren;
        }
    }

    static Node getIndexViaIsA(List<Node> total, boolean[] userIdex, boolean isA) {
        for (int i = 0; i < total.size(); i++) {
            Node node = total.get(i);
            int index = node.index;
            if (!userIdex[index] && node.isA) {
                return node;
            }
        }
        return null;
    }


    static boolean[][][] initUsedTable(int m, int n, List<Node> total) {
        boolean[][][] usedTable = new boolean[m][n][];
        int length = total.size() / 2;
        //遍历total，记录 a，b 中取出数据的个数
        int acount = 0;
        int bcount = 0;
        usedTable[0][0] = new boolean[length];
        //初始化第一行和第一列
        for (int i = 0; i < m + n; i++) {
            Node node = total.get(i);
            int index = node.index;
            if (node.isA) {  //a
                if (acount++ < m) {
                    boolean[] pre = usedTable[acount - 1][0];
                    usedTable[acount][0] = pre.clone();
                    usedTable[acount][0][index] = true;
                }
            } else {  //b
                if (bcount++ < n) {
                    boolean[] pre = usedTable[0][bcount - 1];
                    usedTable[0][bcount] = pre.clone();
                    usedTable[0][bcount][index] = true;
                }
            }
        }
        return usedTable;
    }

    static List<Node> megerArr(int[] a, int[] b) {
        List<Node> total = new ArrayList<>();
        addTotal(a, true, total);
        addTotal(b, false, total);
        Collections.sort(total, Comparator.comparing(Node::getVal).reversed());
        return total;
    }

    static void addTotal(int[] a, boolean isA, List<Node> total) {
        for (int i = 0; i < a.length; i++) {
            Node node = new Node();
            node.val = a[i];
            node.index = i;
            node.isA = isA;
            total.add(node);
        }
    }
}

class Node {
    public int val;
    public int index;
    public boolean isA;

    public int getVal() {
        return this.val;
    }
}
